package _11_整理题目._6_模拟设计._多数之和;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/3sum/
 *
 * 找出所有和为 0 的三个数，不能出现重复答案，数组中的数每个只能用一次
 *
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 *
 * 思路：
 *      0、边界值，当数组长度 < 3 时，直接 return
 *      1、排序
 *      2、定 1，双指针，去重
 *          首先 i 要去重，如果 nums[i]==nums[i+1] i++
 *          其次 确定了 i 后，让 left = i+1，right = n-1
 *          最后 当 target==sum 时，对 left++，和 right-- 也要去重
 *              即 while(left < right && nums[left]==nums[left+1]) left++;
 *
 */
public class _031_三数之和 {

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        if(n < 3) return new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0; i<n-2; i++) {
            if(i > 0 && nums[i] == nums[i-1]) continue;

            int left = i+1, right = n-1;
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if(sum < 0) {
                    left++;
                } else if(sum > 0) {
                    right--;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while(left < right && nums[left]==nums[left+1]) left++;
                    while(left < right && nums[right]==nums[right-1]) right--;
                    left++;
                    right--;
                }
            }
        }
        return result;
    }

    @Test
    public void main() {
        int[] nums = {-1,0,1,2,-1,-4};
        List<List<Integer>> res = threeSum(nums);
        for (List<Integer> re : res) {
            System.out.println(re);
        }
    }
}
